#define _CRT_SECURE_NO_WARNINGS 1


#include<vector>
#include<iostream>

using namespace std;

int get_random(vector<int>& v, int left, int right)
{
    int r = rand();
    return v[r % (right - left + 1) + left];
}

void QuickSort(vector<int>& v, int l, int r, int k)
{
    if (l >= r)
    {
        return;
    }
    int key = get_random(v, l, r);
    int i = l, left = l - 1, right = r + 1;
    while (i < right)
    {
        if (v[i] < key)
        {
            swap(v[++left], v[i++]);
        }
        else if (v[i] > key)
        {
            swap(v[--right], v[i]);
        }
        else
        {
            i++;
        }
    }
    int a = left - l + 1;
    int b = right - left - 1;
    if (a > k)
    {
        QuickSort(v, l, left, k);
    }
    else if (a + b >= k)
    {
        return;
    }
    else
    {
        QuickSort(v, right, r, k - a - b);
    }
}

vector<int> inventoryManagement(vector<int>& stock, int cnt)
{
    srand(time(nullptr));
    QuickSort(stock, 0, stock.size() - 1, cnt);
    return { stock.begin(), stock.begin() + cnt };
}

int main()
{
    vector<int> v = { 0,0,1,2,4,2,2,3,1,4 };
    vector<int> ret = inventoryManagement(v, 8);
    for (auto& e : ret)
    {
        cout << e << ' ';
    }
    cout << endl;

    return 0;
}